401，删除二叉搜索树中的节点

Original 山大王wld 数据结构和算法 2022-05-01

收录于合集 #算法图文分析 161个

I wanted to live deep and suck out all the marrow of life.

我希望活得深刻，吸取生命中所有精华。

问题描述

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

示例:

root = [5,3,6,2,4,null,7]
key = 3

5
/ \
3 6
/ \ \
2 4 7

给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。

一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。

5
/ \
4 6
/ \
2 7

另一个正确答案是 [5,2,6,null,4,null,7]。

5
/ \
2 6
\ \
4 7

问题分析

二叉搜索树的特点是左子树的值都比他小，右子树的值都比他大，删除一个节点之后我们还要保证二叉搜索树的这个特点不变。如果要删除一个结点，我们先要找到这个节点，然后才能删除，但这里要分几种情况。

如果要删除的节点是叶子节点，我们直接删除即可。
如果删除的结点不是叶子节点，并且有一个子节点为空，我们直接返回另一个不为空的子节点即可。
如果删除的结点不是叶子节点，并且左右子树都不为空，我们可以用左子树的最大值替换掉要删除的节点或者用右子树的最小值替换掉要删除的节点都是可以的。

这里使用递归的方式是最容易理解的，我们来看下代码

 1public TreeNode deleteNode(TreeNode root, int key) {
 2    if (root == null)
 3        return null;
 4    //通过递归的方式要先找到要删除的结点
 5    if (key < root.val) {
 6        //要删除的节点在左子树上
 7        root.left = deleteNode(root.left, key);
 8    } else if (key > root.val) {
 9        //要删除的节点在右子树上
10        root.right = deleteNode(root.right, key);
11    } else {
12        //找到了要删除的节点。
13        //如果左子树为空，我们只需要返回右子树即可
14        if (root.left == null)
15            return root.right;
16        //如果右子树为空，我们只需要返回左子树即可
17        if (root.right == null)
18            return root.left;
19        //说明两个子节点都不为空，我们可以找左子树的最大值，
20        //也可以找右子树的最小值替换
21
22        //这里是用右子树的最小值替换
23        //TreeNode minNode = findMin(root.right);
24        //root.val = minNode.val;
25        //root.right = deleteNode(root.right, root.val);
26
27        //这里是用左子树的最大值替换
28        TreeNode maxNode = findMax(root.left);
29        root.val = maxNode.val;
30        root.left = deleteNode(root.left, root.val);
31    }
32    return root;
33}
34
35//    找右子树的最小值
36//    private TreeNode findMin(TreeNode node) {
37//        while (node.left != null)
38//            node = node.left;
39//        return node;
40//    }
41
42//找左子树的最大值
43private TreeNode findMax(TreeNode node) {
44    while (node.right != null)
45        node = node.right;
46    return node;
47}

上面节点删除的时候我们使用左子树的最大值或者右子树的最小值替换都是可以的。其实我们还可以改一下，如果要删除结点左右子树只要有一个为空，我们就返回另一棵子树，如果都不为空，我们可以让左子树成为右子树最小结点的左子树或者让右子树成为左子树最大结点的右子树，我们来看下代码。

 1public TreeNode deleteNode(TreeNode root, int key) {
 2    if (root == null)
 3        return null;
 4    if (root.val > key) {
 5        //要删除的节点在左子树上
 6        root.left = deleteNode(root.left, key);
 7    } else if (root.val < key) {
 8        //要删除的节点在右子树上
 9        root.right = deleteNode(root.right, key);
10    } else {
11        //找到要删除的结点之后
12        if (root.left == null)
13            return root.right;
14        if (root.right == null)
15            return root.left;
16
17        /*
18        //左右子树都不为空，找到要删除结点右子树的最小值
19        TreeNode rightSmallest = root.right;
20        while (rightSmallest.left != null)
21            rightSmallest = rightSmallest.left;
22        //这个最小值对应的节点一定是没有左子树的，
23        // 如果有他肯定不是最小的，然后让删除结点的
24        //左子树成为这个最小值的左子树
25        rightSmallest.left = root.left;
26        //直接返回要删除结点的右子树
27        return root.right;
28         */
29
30        //左右子树都不为空，找到要删除结点左子树的最大值
31        TreeNode leftBig = root.left;
32        while (leftBig.right != null)
33            leftBig = leftBig.right;
34        //这个最大值对应的节点一定是没有右子树的，
35        // 如果有他肯定不是最大的，然后让删除结点的
36        //右子树成为这个最大值的右子树
37        leftBig.right = root.right;
38        //直接返回要删除结点的左子树
39        return root.left;
40    }
41    return root;
42}